// 两数之和
const n = [2,7,11,15], target = 9;
// const n = [1,1,1,2,2,3,3],target = 4;
function twoSum(nums, target) {
  nums = nums.sort((a, b) => a - b);
  let left = 0, right = nums.length - 1;
  let res = [];
  while(left < right) {
    let sum = nums[left] + nums[right];
    let leftv = nums[left], rightv = nums[right];
    if (sum < target) {
      left++;
      while(left < right && nums[left] == leftv) left++;
    } else if (sum > target) {
      right--;
      while(left < right && nums[right] == rightv) right--;
    } else {
      res.push([left, right]);
      while(left < right && nums[left] == leftv) left++;
      while(left < right && nums[right] == rightv) right--;
    }
  }
  return res;
}
console.log(twoSum(n, target));

function twoSum2(nums, target, start = 0) {
  let left = start, right = nums.length - 1;
  let res = [];
  while(left < right) {
    let sum = nums[left] + nums[right];
    let leftv = nums[left], rightv = nums[right];
    if (sum < target) {
      while(left < right && nums[left] == leftv) left++;
    } else if (sum > target) {
      while(left < right && nums[right] == rightv) right--;
    } else {
      res.push([nums[left], nums[right]]);
      while(left < right && nums[left] == leftv) left++;
      while(left < right && nums[right] == rightv) right--;
    }
  }
  return res;
}

function threeSum(nums, target) {
  nums = nums.sort();
  let res = [];
  let n = nums.length;
  for(let i = 0; i < n; i++) {
    let triple = twoSum2(nums, target - nums[i], i + 1);
    for(let v of triple) {
      v.push(nums[i]);
      res.push(v);
    }
    while (i < n - 1 && nums[i] == nums[i + 1]) i++;
  }

  return res;
}
const n2 = [-1,0,1,2,-1,-4], t2 = 0;
console.log(threeSum(n2, t2));

function twoSum3(nums, target) {
  nums = nums.sort((a, b) => a - b);

  let left = 0, right = nums.length - 1;
  let res = []
  while(left < right) {
    let sum = nums[left] + nums[right];
    if (sum == target) {
      res.push([left, right]);
      left++;
      right--;
    } else if (sum < target){
      left++;
    } else if (sum > target) {
      right--;
    }
  }
  return res;
}

console.log(twoSum3(n, target));

function twoSum4(nums, target, start = 0) {
  let left = start, right = nums.length - 1;
  while(left < right) {
    let sum = nums[left] + nums[right];
    if (sum < target) {
      left++;
    } else if (sum > target) {
      right--;
    } else {
      return [nums[left], nums[right]];
    }
  }
  return [];
}

function threeSum2 (nums, target) {
  nums = nums.sort((a, b) => a - b);
  let res = [];
  let n = nums.length;
  for(let i = 0; i < n; i++) {
    let triple = twoSum4(nums, target - nums[i], i + 1);

    if (triple.length > 0) {
      triple.push(nums[i]);
      res.push(triple);
    }
  }

  return res;
}

const res1 = [-1,0,1,2,-1,-4], t4 = 0;
console.log(threeSum2(res1 , t4), 'kkk');
